package com.utils;

import java.util.ArrayList;
import java.util.List;

import com.graph.*;

public class Decomposer {
	
	public List<Star> Dec(Graph Q) {
		// initialize SQ, R
		List<Vertex> R = new ArrayList<Vertex>();
		List<Star> SQ = new ArrayList<Star>();
		// while Q has edges do
		while (Q.hasEdge()) {
			Vertex max_u = null;
			Vertex max_v = null;
			float max_s = 0.0f;
			if (R.isEmpty()) {
				// select an edge (u,v) such that s(u)+s(v) is the largest
				for (Edge e : Q.getEdges()) {
					Vertex u = e.getSrc();
					Vertex v = e.getDst();
					float cur_s = s(u) + s(v);
					if (cur_s > max_s) {
						max_s = cur_s;
						max_u = u;
						max_v = v;
					}
				}
			} else {
				// select an edge (u,v) such that u in R and s(u)+s(v) is the largest
				for (Vertex u : R) {
					for (Edge e : Q.getEdgesBySrc(u)) {
						Vertex v = e.getDst();
						float cur_s = s(u) + s(v);
						if (cur_s > max_s) {
							max_s = cur_s;
							max_u = u;
							max_v = v;
						}
					}
				}
			}
			
			if (max_u == null || max_v == null) {
				return null;
			}
			// Tu = the stars rooted at u
			Star Tu = new Star(max_u, Q.getEdgesBySrc(max_u), Q.getLabelToAttrs());
			// add Tu to SQ
			SQ.add(Tu);
			// R = R ∪ neighbor(u)
			R.removeAll(Q.getNeighbors(max_u));
			R.addAll(Q.getNeighbors(max_u)); 
			// remove Tu from Q
			Q.removeVertex(max_u);
			
			if (Q.getDegree(max_v) > 0) {
				// Tv = the stars rooted at v
				Star Tv = new Star(max_v, Q.getEdgesBySrc(max_v), Q.getLabelToAttrs());
				// add Tv to SQ
				SQ.add(Tv);
				// remove Tv from Q
				Q.removeVertex(max_v);
				// R = R ∪ neighbor(v);
				R.removeAll(Q.getNeighbors(max_v));
				R.addAll(Q.getNeighbors(max_v)); 
			}
			
			// remove u,v and all nodes with degree 0 from R
			R.remove(max_u);
			R.remove(max_v);
			int i = 0;
			while (i < R.size()) {
				if (Q.getDegree(R.get(i)) == 0) {
					R.remove(i);
					continue;
				}
				i++;
			}
		}
		
		return SQ;
	}
	
	float s(Vertex v) {
		switch(v.getLabel()) {
		case "Customer": 
			return 0.5f;
		case "Product": 
			return 0.25f;
		case "Brand": 
			return 0.1f;
		default: 
			return 0.0f;
		}
	}
}

